1. Field of the Invention
The present invention relates to electronic computers, and, more particularly, to control in multiprocessor systems.
2. Description of the Related Art
Attempts to understand the functioning of the human brain have led to various "neural network" models in which large numbers of simple computing elements ("neurons") are interconnected (by "synapses") to form a connectionist machine. As with all connectionist machines, neural networks use fine-grained parallelism to perform complex functions at very high speed. This high effective computing bandwidth can be applied to compute-bound problems such as finite-element analysis, image processing, adaptive signal processing, constrained optimization, associative memory, and artifical intelligence.
Neural network models roughly presume each neuron can exist in one of two states (quiescent and firing) with the state determined by the states of directly-connected neurons (e.g., if enough directly-connected neurons are firing, then the original neuron should switch to or be in the firing state). The models may be simple feedforward layered structures with an input layer of neurons, one or more hidden layers of neurons, and an output layer of neurons. Other models have feedback among the neurons and correspondingly more involved behavior.
The structure of any neural network can be defined by directed graphs as illustrated in FIG. 1. The vertices of the graph represent the computing elements and have associated parameters, and the edges of the graph define the communication paths among the computing elements and also have associated paramenters. Also, input and output paths connected to each vertex are shown. A vertex and its associated parameters define a neuron (labelled N.sub.j) and an edge with its associated parameters define a synapse (labelled S.sub.ij for the path from N.sub.j to N.sub.i) between neurons. The synapses are not just communication paths, but also modify the signals propagated between neurons. If we assume that a synapse value of zero (e.g., S.sub.ij =0) corresponds to an absence of connection between neurons (e.g., from N.sub.j to N.sub.i), then any neural network configuration may be represented more generally by a complete graph of N neurons together with N.sup.2 synapses. Most neural networks do in fact have on the order of N.sup.2 connectivity, so the number of parameters required to define a network state increases as a power of the size of the model.
The output of a neuron is a function of its internal state plus the inputs it receives from its synaptic connections. Each neuron is defined to receive an external input, serve as an external output, or be externally inacessible (hidden). Neurons need not operate synchronously, have uniform connectivity, nor obey the same rules for change of state. The state of a neuron by a simple numerical value or by more complex data structures.
For example, J. Hopfield, Neural Networks and Physical Systems with Emergent Collective Computational Abilities, 79 Proc. Natl. Acad. Sci. USA 2554 (1982) describes a neural network model with N neurons each of which has the value 0 or 1 (corresponding to the quiescent state or to the firing state, respectively), so the state of the network is then an N-component vector V=[V.sub.1, V.sub.2, . . . , V.sub.N ] of 0's and 1's which depends upon time. The neuron interconnections are described by a matrix S.sub.i,j defining the influence of the j.sup.th neuron on the i.sup.th neuron. The state of the network evolves in time as follows: each neuron i has a fixed threshold .theta..sub.i and readjusts its state V.sub.i randomly in time by setting V.sub.i equal to 0 or 1 depending on whether ##EQU1## is negative or positive. All neurons have the same average rate of readjustment, and the readjustments define a dynamical flow in state space.
With the assumption that S.sub.i,j is symmetric, the potential function ##EQU2## can be used to show that the flow of the network is to local minima of the potential function. Further, with a given set of uncorrelated N-component vectors U.sup.1, U.sup.2, . . . , U.sup.8, a S.sub.i,j can be defined by ##EQU3## and with the thresholds equal to 0, these U.sup.k are the fixed points of the flow and thus stable states of the network. This is a type of "outer product storage" of the vectors U.sup.1, U.sup.2, . . . , U.sup.8. Such a network can act as a content-addressable memory as follows: the memories to be stored in the network are used to construct the U.sup.k and hence S.sub.i,j, so the stored memories are fixed points of the flow. Then a given partial memory is input by using it to define the initial state of the network, and the state will flow usually to the closest fixed point/stable state U.sup.k which is then the memory recalled upon input of the partial memory.
Further analysis and modified network models appear in, for example, J. Hopfield et al, Computing with Neural Circuits: A Model, 233 Science 625 (1986) and J. Hopfield, Neurons with Graded Response Have Collective Computational Properties like Those of Two-State Neurons, 81 Proc. Natl. Acad. Sci. USA 3088 (1984).
Synapses are usually modified by a recursive algorithm that depends upon the local response of the network to a set of external inputs. After this "training" phase, the network can be used to perform a function by presenting certain neurons with input data and then allowing the network to evolve as previously described. Most algorithms allow very high internal parallelism during the "compute" phase and reach a near steady state in just a few propagation delays of information through the network.
For example, J. Anderson, Cognitive Capabilities of a Parallel System, NATO Advanced Research Workshop (Mar. 3, 1985) describes the Brain State in a Box (BSB) neural network model which includes outer-product storage, Widrow-Hoff learning, and a ramped-threshold recall algorithm. That is, the matrix of interconnection strengths, S.sub.i,j, is modified to learn a new vector V.sub.j by ##EQU4## where .eta. is a learning constant and N is number of neurons. The learning constant is roughly the inverse of the number of times the matrix must be trained on a given vector before it fully learns the vector. The smaller the learning constant, the finer the resolution of the average direction for a learned state but the more times the input vectors must be trained. The learning procedure saturates when .DELTA.S.sub.i,j is close to zero, which implies that the vector is close to being an eigenvector of the matrix with an eigenvalue near 1.
Recall of a learned (stored) vector given an input vector U.sub.j is by the following iterative process that converges towards an eigenvector: ##EQU5## where the "Limit" function clamps the values in the range from -1 to 1. The constants .gamma. and .beta. measure the feedback and signal decay in the algorithm. This synchronous recall algorithm replaces the dynamical flow of the Hopfield model. The usual applications of the BSB neural network such as data bases with words and letters encoded as their ASCII representations require binary neurons as in the first Hopfield model.
A problem with neural networks is the lack of efficient nonbiological hardware. Further, the simulation of neural networks with standard digital computers demands extreme computing power. For example, consider a neural network composed of 256 by 256 fully interconnected neurons (large enough to assign one neuron to each pixel in a low-resolution video camera image) would contain over four billion synaptic connections. A real-time simulation of the processing of a single video frame by this network would require a minimum computing rate of over 250 billion synapse operations per second. And the number of parameters needed to define a neural network tends to grow as a power of the network size, and the communication cost in parallel processor computers overwhelms the computer.